#ifndef SPW_VECTOR_H
#define SPW_VECTOR_H

#include <memory/spw_memory.h>
#include <iterator/spw_iterator.h>
#include <spw_config.h>
#include <utility/spw_utility.h>
#include <exception/spw_stdexcept.h>
#include <algorithm/spw_algobase.h>
#include <type_traits>
#include <initializer_list>
#include <cassert>
namespace spwstd {

template<typename T, typename Alloc>
struct VectorBase_in {
    using AllocT = Alloc;
    using Pointer = T*;

/* vector 实现内部数据 */
struct VectorImplData_in {
    /* vector内部所有数据 */
    Pointer start_;
    Pointer finish_;
    Pointer end_of_storage_;

    VectorImplData_in() noexcept
        : start_{}, finish_{}, end_of_storage_{} { }

    VectorImplData_in(VectorImplData_in&& other) noexcept
        : start_{other.start_}, finish_{other.finish_}, end_of_storage_{other.end_of_storage_}
    {
        other.start_ = other.finish_ = other.end_of_storage_ = Pointer{};
    }

    void CopyDate_in(VectorImplData_in const& other) noexcept {
        start_ = other.start_;
        finish_ = other.finish_;
        end_of_storage_ = other.end_of_storage_;
    }

    void SwapDate_in(VectorImplData_in& other) noexcept {
        VectorImplData_in tmp;
        tmp.CopyDate_in(*this);
        CopyDate_in(other);
        other.CopyDate_in(tmp);
    }
};

/* vector impl */
struct VectorImpl_in
    : public AllocT, public VectorImplData_in 
{
    VectorImpl_in() = default;
    VectorImpl_in(AllocT const& othera) noexcept
        : AllocT{othera}
    { }
    VectorImpl_in(VectorImpl_in&& other) noexcept
        : AllocT{spwuti::move(other)}, VectorImplData_in{spwuti::move(other)}
    { }
    VectorImpl_in(AllocT&& othera) noexcept
        : AllocT{spwuti::move(othera)}
    { }
    VectorImpl_in(AllocT&& oalloc, VectorImpl_in&& other) noexcept
        : AllocT{spwuti::move(oalloc)}, VectorImplData_in{spwuti::move(other)}
    { }
};

    AllocT& GetAllocator() noexcept { return this->impl_; }
    const AllocT& GetAllocator() const noexcept { return this->impl_; }

    VectorBase_in() = default;
    VectorBase_in(VectorBase_in&&) = default;

    VectorBase_in(const AllocT& othera) noexcept : impl_{othera} { }

    VectorBase_in(spwconfig::size_t n): impl_{} { CreateStorage_in(n); }
    VectorBase_in(spwconfig::size_t n, const AllocT& a): impl_{a} { CreateStorage_in(n); }
    VectorBase_in(AllocT&& othera) noexcept : impl_{spwuti::move(othera)} { }

public:
    VectorImpl_in impl_;

    Pointer Allocate_in(spwconfig::size_t n) {
        return n != 0 ?
            spwstd::AllocInterface<typename spwstd::AllocTraits<AllocT>::ValueType, AllocT>::s_allocate(n) : Pointer{};
    }

    void Deallocate_in(Pointer ptr, spwconfig::size_t n) {
        if(ptr)
            spwstd::AllocInterface<typename spwstd::AllocTraits<AllocT>::ValueType, AllocT>::s_deallocate(ptr, n);
    }

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter> >
    void Destory_in(InputIter first, InputIter last)
    {
        auto n = last - first;
        for(auto i=0; i<n; ++i) {
            spwstd::AllocInterface<typename spwstd::AllocTraits<AllocT>::ValueType, AllocT>::s_destroy(first + i);
        }
    }

protected:
    void CreateStorage_in(spwconfig::size_t n) 
    {
        this->impl_.start_ = this->Allocate_in(n);
        this->impl_.finish_ = this->impl_.start_;
        this->impl_.end_of_storage_ = this->impl_.start_ + n;
    }
};

/* Vector */
template<typename T, typename Alloc=spwstd::DefaultAlloc<T>>
class Vector: protected VectorBase_in<T, Alloc> {
    using Base = VectorBase_in<T, Alloc>;

public:
    using ValueType = T;
    using Pointer = T*;
    using ConstPointer = const T*;
    using Refer = T&;
    using ConstRefer = const T&;
    using Iter = spwstd::NormalIterator<Pointer, Vector>;
    using ConstIter = spwstd::NormalIterator<ConstPointer, Vector>;
    using SizeType = spwconfig::size_t;
    using DifferType = spwconfig::ptrdiff_t;
    using AllocT = Alloc;

public:
    Vector() = default;

    explicit Vector(SizeType n, const ValueType& value = ValueType{}, const AllocT& a=AllocT{})
        : Base{n, a}
    {
        this->impl_.finish_ = spwstd::uninitializedFillN(this->impl_.start_, n, value);
    }

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter> >
    Vector(InputIter first, InputIter last, const AllocT& a=AllocT{})
        : Base{static_cast<SizeType>(last-first), a}
    {
        this->impl_.finish_ = spwstd::uninitializedCopy(first, last, this->impl_.start_);
    }

    Vector(std::initializer_list<ValueType> l, const AllocT& a=AllocT{})
        : Base{l.size(), a}
    {
        this->impl_.finish_ = spwstd::uninitializedCopy(l.begin(), l.end(), this->impl_.start_);
    }

    Vector(const Vector& other, const AllocT& a=AllocT{})
        : Base{other.Size(), a}
    {
        this->impl_.finish_ = spwstd::uninitializedCopy(other.Begin(), other.End(), this->impl_.start_);
    }

    Vector(Vector&&) noexcept = default;

    ~Vector() noexcept
    {
        this->Destory_in(this->Begin(), this->End());
        this->Deallocate_in(this->impl_.start_, this->Capacity()); 
    }

    /* operator= */
    Vector& operator=(const Vector& x);
    Vector& operator=(Vector&& x);

public:
    using Base::GetAllocator;
    using Base::Deallocate_in;
    /* 访问 at, operator[], front, back, data */
    Refer operator[](SizeType n) noexcept
    {
        return *(this->impl_.start_ + n);
    }

    ConstRefer operator[](SizeType n) const noexcept
    {
        return *(this->impl_.start_ + n);
    }

    // 带越界检测
    Refer At(SizeType n)
    {
        RangeCheck_in(n);
        return (*this)[n];
    }

    ConstRefer At(SizeType n) const
    {
        RangeCheck_in(n);
        return (*this)[n];
    }

    Refer Front() noexcept
    {
        assert(!this->Empty());
        return *Begin();
    }

    ConstRefer Front() const noexcept
    {
        assert(!this->Empty());
        return *Begin();
    }

    Refer Back() noexcept
    {
        assert(!this->Empty());
        return *(End()-1);
    }

    ConstRefer Back() const noexcept
    {
        assert(!this->Empty());
        return *(End()-1);
    }

    Pointer Data() noexcept
    {
        return DataPtr_in(this->impl_.start_);
    }

    /* 迭代器 begin, end, cbegin, cend */
    Iter Begin() noexcept 
    { return Iter{this->impl_.start_}; }

    ConstIter Begin() const noexcept 
    { return ConstIter{this->impl_.start_}; }

    Iter End() noexcept
    { return Iter{this->impl_.finish_}; }

    ConstIter End() const noexcept 
    { return ConstIter{this->impl_.finish_}; }

    ConstIter Cbegin() const noexcept 
    { return ConstIter{this->impl_.start_}; }

    ConstIter Cend() const noexcept 
    { return ConstIter{this->impl_.finish_}; }

    /* 容量 empty, size, capacity, reserve, shrink_to_fit */
    SizeType Size() const noexcept 
    { return static_cast<SizeType>(this->impl_.finish_ - this->impl_.start_); }

    SizeType Capacity() const noexcept 
    { return static_cast<SizeType>(this->impl_.end_of_storage_ - this->impl_.start_); }

    bool Empty() const noexcept 
    { return Begin() == End(); }

    void Reserve(SizeType n);

    void ShrinkToFit();

    /* 修改 TODO: clear, insert, erase, push_back, pop_back, resize, -swap */
    void Clear() noexcept
    {
        this->Destory_in(this->Begin(), this->End());
        this->impl_.finish_ = this->impl_.start_;
    }

    void Resize(SizeType new_size, const ValueType& x = ValueType{});

    Iter Erase(Iter pos);
    Iter Erase(Iter first, Iter last);

    Iter Insert(ConstIter pos, const ValueType& x);

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter> >
    Iter Insert(ConstIter pos, InputIter first, InputIter last);

    void PopBack() noexcept
    {
        assert(!this->Empty());
        --this->impl_.finish_;
        this->Destory_in(this->End()-1, this->End());
    }

    void PushBack(const ValueType& x);
    //void PushBack(ValueType&& x);

protected:
    // 检测初始化时，判断分配器是否可以分配n个T
    static SizeType s_checkInitLen(SizeType n, const AllocT& a)
    { 
        if (n > s_allocMaxSize(a)) {
            throw spwstd::spwexcept::LengthError("cannot create std::vector larger than maxsize");
        }
        return n;
    }

    static SizeType s_allocMaxSize(const AllocT& a = AllocT{}) noexcept
    { return a.maxSize(); }

    // 范围检测
    void RangeCheck_in(SizeType n) const
    {
        if (n >= this->Size()) 
            throw spwexcept::OutOfRange("outofrange");
    }

    Pointer DataPtr_in(Pointer ptr) const
    {
        return Empty() ? nullptr : ptr;
    }

    // 重新分配一个capacity = n的空间，把原来的复制到新空间
    void ReVector_in(SizeType n);

    SizeType CheckLen_in(SizeType n) const
    {
        if (s_allocMaxSize()-Size() < n)
            throw spwstd::spwexcept::LengthError("lengtherror");
        const SizeType len = Size() + (Size()>n ? Size() : n);
        return (len < Size() || len > s_allocMaxSize()) ? s_allocMaxSize() : len;
    }
};

template<typename T, typename Alloc>
void Vector<T, Alloc>::
ReVector_in(SizeType n)
{
    Pointer new_start = this->Allocate_in(n);
    Pointer new_finish = spwstd::uninitializedCopy(this->Begin(), this->End(), new_start);
    this->Clear();
    this->Deallocate_in(this->impl_.start_, this->Capacity());
    this->impl_.start_ = new_start;
    this->impl_.finish_ = new_finish;
    this->impl_.end_of_storage_ = this->impl_.start_ + n;
}

template<typename T, typename Alloc>
Vector<T, Alloc>& Vector<T, Alloc>::operator=(const Vector<T, Alloc>& other)
{
    if (&other != this) {
        const SizeType other_len = other.Size();
        if (other_len > Capacity()) {
            this->Destory_in(this->Begin(), this->End());
            this->Deallocate_in(this->impl_.start_, this->Capacity());
            this->CreateStorage_in(other_len);
            this->impl_.finish_ = spwstd::uninitializedCopy(other.Begin(), other.End(), this->impl_.start_);
        } else if (Size() >= other_len) {
            Iter tmp_finsh = spwstd::uninitializedCopy(other.Begin(), other.End(), Begin());
            this->Destory_in(tmp_finsh, this->End());
            this->impl_.finish_ = &*tmp_finsh;
        } else { // size() < other_len < capacity()
            this->impl_.finish_ = spwstd::uninitializedCopy(other.Begin(), other.End(), this->impl_.start_);
        }
    }
    return *this;
}

template<typename T, typename Alloc>
Vector<T, Alloc>& Vector<T, Alloc>::operator=(Vector<T, Alloc>&& other)
{
    Vector<T, Alloc> tmp;
    this->impl_.SwapDate_in(other.impl_);
    other.impl_.SwapDate_in(tmp.impl_);
    return *this;
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::Reserve(SizeType n)
{
    if (n > s_allocMaxSize())
        throw spwstd::spwexcept::LengthError("vector::reserve");
    // 只有n > capacity时，才会起作用
    if (this->Capacity() < n) {
        this->ReVector_in(n);
    }
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::
ShrinkToFit() 
{
    SizeType size = this->Size();
    if (size){
        this->ReVector_in(size);
    } else {
        this->Deallocate_in(this->impl_.start_, this->Capacity());
        this->impl_.start_ = nullptr;
        this->impl_.finish_ = nullptr;
        this->impl_.end_of_storage_ = nullptr;
    }
}

template<typename T, typename Alloc>
void Vector<T, Alloc>:: 
Resize(SizeType new_size, const ValueType& x)
{
    SizeType old_size = this->Size();
    if (new_size > old_size) {
        this->ReVector_in(new_size);
        spwstd::uninitializedFillN(this->Begin()+old_size, new_size-old_size, x);
        this->impl_.finish_ = this->impl_.start_ + new_size;
    } else if (new_size < old_size) {
        this->Erase(this->Begin()+new_size,this->End());
    }
}

template<typename T, typename Alloc>
typename Vector<T, Alloc>::Iter 
Vector<T, Alloc>::Erase(Iter pos)
{
    if (pos+1 != this->End())
        spwstd::uninitializedCopy(pos+1, this->End(), pos);
    --this->impl_.finish_;
    return pos;
}

template<typename T, typename Alloc>
typename Vector<T, Alloc>::Iter
Vector<T, Alloc>::Erase(Iter first, Iter last)
{
    if (first != last) {
        spwstd::uninitializedCopy(last, this->End(), first);
    }
    this->impl_.finish_ -= last-first;
    return first;
}

template<typename T, typename Alloc>
typename Vector<T, Alloc>::Iter
Vector<T, Alloc>::Insert(ConstIter pos, const ValueType& x)
{
    Iter tmp_pos = this->Begin() + (pos - this->Cbegin());
    SizeType new_size = this->Size() + 1;
    if(new_size <= this->Capacity()) {
        spwalg::copyBackward(tmp_pos, this->End(), this->End()+1);
        ++this->impl_.finish_;
        *tmp_pos = x;
    } else {
        Pointer tmp_alloc = this->Allocate_in(new_size);
        Pointer tmp_finsh = spwstd::uninitializedCopy(this->Begin(), tmp_pos, tmp_alloc);
        *tmp_finsh = x;
        ++tmp_finsh;
        this->impl_.finish_ = spwstd::uninitializedCopy(tmp_pos, this->End(), tmp_finsh);
        this->impl_.start_ = tmp_alloc;
        this->impl_.end_of_storage_ = this->impl_.start_ + new_size;
    }
    return tmp_pos;
}

template<typename T, typename Alloc>
template<typename InputIter, typename>
typename Vector<T, Alloc>::Iter
Vector<T, Alloc>::Insert(ConstIter pos, InputIter first, InputIter last)
{
    SizeType will_insert_n = last - first;
    SizeType new_size = this->Size() + will_insert_n;
    Iter tmp_pos = this->Begin() + (pos-this->Cbegin());
    if(new_size <= this->Capacity()) {
        spwalg::copyBackward(tmp_pos, this->End(), this->End()+will_insert_n);
        for(;first!=last; ++first, ++tmp_pos) {
            ++this->impl_.finish_;
            *tmp_pos = *first;
        }
    } else {
        Pointer tmp_alloc = this->Allocate_in(new_size);
        Pointer tmp_finsh = spwstd::uninitializedCopy(this->Begin(), tmp_pos, tmp_alloc);
        for(;first!=last; ++first, ++tmp_finsh) {
            *tmp_finsh = *first;
        }
        this->impl_.finish_ = spwstd::uninitializedCopy(tmp_pos, this->End(), tmp_finsh);
        this->impl_.start_ = tmp_alloc;
        this->impl_.end_of_storage_ = this->impl_.start_ + new_size;
    }
    return tmp_pos;
}

template<typename T, typename Alloc>
void Vector<T, Alloc>::PushBack(const ValueType& x)
{
    if (this->impl_.finish_ != this->impl_.end_of_storage_) {
        *this->impl_.finish_ = x;
        ++this->impl_.finish_;
    } else {
        const SizeType len = CheckLen_in(1);
        this->ReVector_in(len);
        *this->impl_.finish_ = x;
        ++this->impl_.finish_;
    }
}
} // spwstd
#endif // SPW_VECTOR_H
